//
//  Problem324.swift
//  LeetCode
//
//  Created by 武侠 on 2023/6/28.
//  Copyright © 2023 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 324. 摆动排序 II 中等
 
 给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
 你可以假设所有输入数组都可以得到满足题目要求的结果。
 示例 1：
     输入：nums = [1,5,1,1,6,4]
     输出：[1,6,1,5,1,4]
     解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。
 示例 2：
     输入：nums = [1,3,2,2,3,1]
     输出：[2,3,1,3,1,2]
 提示：
 1 <= nums.length <= 5 * 10^4
 0 <= nums[i] <= 5000
 题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

 进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
 */
class Problem324: NSObject {
    func wiggleSort(_ nums: inout [Int]) {
        var list = nums.sorted()
        
        var i = 0, j = 1
        if nums.count % 2 == 0 {
            i = nums.count - 2
            j = nums.count - 1
        } else {
            i = nums.count - 1
            j = nums.count - 2
        }
        
        for n in list {
            if i >= 0 {             // 先排序奇数
                nums[i] = n
                i -= 2
            } else {                // 先排序偶数
                nums[j] = n
                j -= 2
            }
        }
//        print(nums)
    }
}
